<html>
<head><meta http-equiv="Content-Type" content="text/html; charset=GBK">
<title>Lab #4: AST and Translation</title>
<link rel="stylesheet" type="text/css">
</head>

<body>
<font face="Trebuchet MS">
<table width="100%">
<tbody>
  <tr>
<td>
<h1>Lab #4: AST and Translation</h1>
<hr>

<h3>Introduction</h3>

<p>This lab requires you to write a translator program, which 
translates AST of the MiniJava language into another structure 
called AST2. The differences between AST and AST2 are listed below.</p>
<ol>
<li>AST has inheritance of class, but AST2 doesn't, that is, 
AST2 doesn't have "extends" keywords.</li>
<li>Every class in AST2 has method table, which records all 
methods of the class.</li>
</ol>

<p>This lab is divided into two parts: A and B, and part B depends on part A.</p>
<h3>Start</h3>

<p>
To start, you should download this 
<a href="http://home.ustc.edu.cn/~huwei16/lab4.rar">
package</a>,  
in which we have offered you a code skeleton. Here is a brief 
discription of the files:
</p>
<table valign="top" border="1" >
<tr>
    <td>parser/java.grm  </td>
    <td>
	the ML-Yacc specification file, <code>java.grm.sml</code> 
	is generated by the file.
	</td>
  </tr>
  <tr>
    <td><p>parser/parse.fun, .sig</p> </td>
    <td>the definition of Parse functor, it defines a function 
	<code>parse()</code>, which reads the input file and then 
	calls the lexer and parser</td>
  </tr>
  <tr>
    <td >libs/errormsg.sig, .sml</td>
    <td >the definition of error handling facilities, 
    they will be used in the lexer (and later labs)</td>
  </tr>
  <tr>
    <td >ast/ast.fun, .sig</td>
    <td >the definition of AST</td>
  </tr>
  <tr>
    <td >ast/ast2.fun, .sig</td>
    <td >the definition of AST2</td>
  </tr>
  <tr>
    <td >ast/genAST2.fun, .sig</td>
    <td >the definition of functor which translates AST to AST2</td>
  </tr>
  <tr>
    <td>main/main.sig, .sml</td>
    <td>the definition of Main structure, it defines a function
	<code>main()</code>, which will call function 
	<code>parse()</code> defined in <code>parser/parse.fun</code>,
	and another function <code>mainWrap()</code> wraps function 
	<code>main()</code></td>
  </tr>
  <tr>
    <td>call-main.sml </td>
    <td>the entry of whole program</td>
  </tr>
  <tr>
    <td>Test.java </td>
    <td>a sample input file to test your program</td>
  </tr>
</table>

<h2>Part A:  Fields and Methods Sort</h2>

<p>This part requires you to write a sort program, which sorts 
fields and methods separately for classes on AST of the MiniJava language. 
For example, the original code is:</p><pre>
class Mylist{

	public int sort(){
		return 0;
	}
	
	public int search(){
		return 0;
	}
    
	int size;
	int capacity;
}
</pre>
<p>After sorting, the output code is:</p>
<pre>
class Mylist{

	public int search(){
		return 0;
	}
    
	public int sort(){
		return 0;
	}
    
	int capacity;
	int size;
}</pre>

<h3>Your Job</h3>
<ol>
<li>You need to read <code>java.grm</code> and <code>ast.fun</code>. 
Note: this code <code>java.grm</code> is different from that of lab3, 
it adds some actions to build AST for program.
You need to understand how AST is built 
before you proceed.</li>
<li>The code you should modify looks like
<pre>(print"raise Unimplement"; raise Unimplement)</pre>
  So you should find all place marked as this and replace 
  them with your code.</li>
</ol>

<h3>Compile, run, and test</h3>
<ul>
<li><b>Compile the whole program.</b>  After you finish 
the code, run <code>cmd</code>, change the directory to 
lab4, and then run <code>build</code> to build the whole program.</li>
<li><b>Run the whole program.</b> 
Without changing the directory, type<pre>
jc Test.java</pre>It will output two files which are the 
same as <code>Test_ast.java</code> and <code>Test_ast_sorted.java</code>.</li>
</ul>

<h2>Part B: Sub-Class Elimination</h2>

<p>This Section requires you to write a translator from AST to AST2. 
Considering difference between AST and AST2, we need to do the 
following things to accomplish the translating task.</p>
<ol>
<li>remove <code>"extends"</code></li>
<li>establish a method table for every class</li>
</ol>
<p>Now we introduce the key steps of this algorithm.</p> 
<p><b>First</b>, building inheritance trees for AST, for example, 
if we have following code:
<pre>
class A extends B{
	...
}

class C extends B{
	...
}

class D extends A{
	...
}
</pre>
we can build a tree as followed,
<pre>
          <b>B</b>
        /   \
       <b>A</b>     <b>C</b>
      /
     <b>D</b>
</pre>
</p>
<p><b>Second</b>, do a BFS (Breadth First Search) walk on the
tree.</p> For every node in trees, do the following steps: 
<p>(1) If it is a root of a tree, put its methods to its 
method table.</p><p>(2) for every child of the current node, firstly, merge
parent's fields to this child, that is, copy parent's different 
fields to child; secondly, put child's methods to child's method table, 
then merge parent's method table into my method table.</p>

<p>
Here, you must take account of method overwriting.

<p>SMLNJ lib provides <code>Queue</code>, maybe you'd want to use
it, or you can cook your own version.</p>

<h3>Your Job</h3>
<ol>
<li>You need to read <code>ast2.fun</code> and <code>genAST2.fun</code>. 
You need to make it clear the different between 
AST and AST2 before you proceed.</li>
<li>The code you should modify looks like
<pre>(print"raise Unimplement"; raise Unimplement)</pre>
  So you should find all places marked as this and replace 
  them with your code.</li>
</ol>

<h3>Compile, run, and test</h3>
<ul>
<li><b>Compile the whole program.</b>  After you finish the code, 
<u>Note: first you need to change variable <code>doPartB</code> 
to be <code>true</code></u>, then run <code>cmd</code>, 
change the directory to lab4, and then run <code>build</code> 
to build the whole program.</li>
<li><b>Run the whole program.</b> 
Without changing the directory, type<pre>
jc Test.java</pre>It will output two files which are the same 
as <code>Test_ast.java</code>, <code>Test_ast_sorted.java
</code> and <code>Test.java2</code>.</li>
</ul>

<p>
As always, a single test is far from complete. You will want to write 
your own test cases and 
thoroughly test your parser. Repeat the above procedure once 
you modify your code.
</p>

<h3>Handin</h3>
This completes the lab. Hand in your solution to information 
system.

</td>
</tr>
  
</tbody>
</table>
</font>


</body>
</html>
